package com.cdream.basic.algorithm.leetcode.linkedlist;

import java.util.LinkedList;

/**
 * @author cdream
 * @date 6/12/21
 */
public class Question2 {
    // public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //     ListNode cur1 = l1;
    //     ListNode cur2 = l2;
    //     int mod = 0;
    //     ListNode dummy = new ListNode(-1);
    //     ListNode cur = dummy;
    //     while (cur1 != null || cur2 != null || mod != 0) {
    //         if (cur1 == null && cur2 == null) {
    //             cur.next = new ListNode(mod);
    //             mod = 0;
    //         } else if (cur1 == null) {
    //             int sum = cur2.val + mod;
    //             mod = sum / 10;
    //             cur.next = new ListNode(sum % 10);
    //         } else if (cur2 == null) {
    //             int sum = cur1.val + mod;
    //             mod = sum / 10;
    //             cur.next = new ListNode(sum % 10);
    //         } else {
    //             int sum = cur1.val + cur2.val + mod;
    //             mod = sum / 10;
    //             cur.next = new ListNode(sum % 10);
    //         }
    //         cur = cur.next;
    //         if (cur1 != null) {
    //             cur1 = cur1.next;
    //         }
    //         if (cur2 != null) {
    //             cur2 = cur2.next;
    //         }
    //     }
    //     return dummy.next;
    // }
    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        ListNode l2 = new ListNode(4);
        ListNode l3 = new ListNode(3);
        l1.next = l2;
        l2.next = l3;
        ListNode l4 = new ListNode(5);
        ListNode l5 = new ListNode(6);
        ListNode l6 = new ListNode(4);
        l4.next = l5;
        l5.next = l6;
        new Question2().addTwoNumbers(l1,l4);
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 方法1. 链表转字符串，相加后转链表,由于有100个，本方法失效
        // 方法2， 栈来完成
        ListNode head = null;
        LinkedList<ListNode> ll1 = new LinkedList<ListNode>();
        LinkedList<ListNode> ll2 = new LinkedList<>();
        while(l1!=null){
            ll1.push(l1);
            l1 = l1.next;
        }
        while(l2!=null){
            ll2.push(l2);
            l2 = l2.next;
        }
        int round = 0;
        while(!ll1.isEmpty() || !ll2.isEmpty() || round!=0){
            if(ll1.isEmpty() && ll2.isEmpty()){
                ListNode n = new ListNode(round);
                n.next = head;
                head = n;
                round = 0;
            }
            if(ll1.isEmpty() && !ll2.isEmpty() ){
                int sum = round + ll2.poll().val;
                ListNode n = new ListNode(sum % 10);
                n.next = head;
                head = n;
                round = sum / 10;
            }
            if(!ll1.isEmpty() && ll2.isEmpty() ){
                int sum = round + ll1.poll().val;
                ListNode n = new ListNode(sum % 10);
                n.next = head;
                head = n;
                round = sum / 10;
            }
            if(!ll1.isEmpty() && !ll2.isEmpty()){
                int sum = round + ll1.poll().val + ll2.poll().val;
                ListNode n = new ListNode(sum % 10);
                n.next = head;
                head = n;
                round = sum / 10;
            }
        }
        return head;

    }
}
